package history.hot100;

// 34. 在排序数组中查找元素的第一个和最后一个位置:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// 二分查找相关题型：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/yi-wen-dai-ni-gao-ding-er-fen-cha-zhao-j-ymwl/
public class LeetCode_34 {
    public int[] searchRange(int[] nums, int target) {
        int lower = lowerBound(nums, target);
        int upper = upperBound(nums, target);
        if (upper<lower) return new int []{-1,-1};
        return new int[] {lower, upper};
    }

    //计算下边界
    int lowerBound(int []nums, int target) {
        int left = 0, right = nums.length-1;
        while (left<=right) {
            int mid = left+((right-left)>>1);
            if (target<=nums[mid]) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return left;
    }

    //计算上边界
    int upperBound(int []nums, int target) {
        int left = 0, right = nums.length-1;
        while (left<=right) {
            int mid = left+((right-left)>>1);
            if (target<nums[mid]) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        return right;
    }
}
